package com.li.sort.arithmetic;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {
	public static final int SIZE = 10000000;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}
		
		//System.out.println(Arrays.toString(array));
		long time1= System.currentTimeMillis();
		mergeSort(array,0,array.length-1);
		//System.out.println(Arrays.toString(array));
		System.out.println(System.currentTimeMillis()-time1);
	}
	
	/**
	 * n-1趟排序就ok
	 * @param array
	 */
	public static void mergeSort(int[] array,int left,int right){
		if(left==right){
			return;
		}
		int mid = (left+right)/2;
		mergeSort(array,left,mid);
		mergeSort(array,mid+1,right);
		merge(array,left,mid,right);
	}
	
	public static void merge(int[] array,int left,int mid ,int right){
		int[] temp = new int[right -left +1];
		int index = 0;
		int i = left;
		int j = mid+1;
		while(i<=mid && j<=right){
			temp[index++] = array[i] <= array[j] ? array[i++]:array[j++]; 
		}
		while(i<=mid){
			temp[index++] = array[i++];
		}
		while(j<=right){
			temp[index++] = array[j++];
		}
		for(int k=0;k<temp.length;k++){
			array[left++] = temp[k];
		}
	}
	
	public static void swap(int[] array,int i,int j){
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
